package Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 98.验证二叉搜索树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * 有效 二叉搜索树定义如下：
 * ● 节点的左子树只包含 小于 当前节点的数。
 * ● 节点的右子树只包含 大于 当前节点的数。
 * ● 所有左子树和右子树自身必须也是二叉搜索树。
 */
public class isValidBST {
    /**
     * 一刷
     */
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    private boolean isValidBST(TreeNode node, Integer lower, Integer upper) {
        if (node == null) {
            return true;
        }

        int val = node.val;

        if (lower != null && val <= lower) {
            return false;
        }
        if (upper != null && val >= upper) {
            return false;
        }

        // 递归检查右子树，右子树的下限是当前节点的值
        if (!isValidBST(node.right, val, upper)) {
            return false;
        }
        // 递归检查左子树，左子树的上限是当前节点的值
        if (!isValidBST(node.left, lower, val)) {
            return false;
        }
        return true;
    }

    /**
     * 二刷：中序遍历
     */
    public boolean isValidBST2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int pre = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) <= pre)
                return false;
            else
                pre = list.get(i);
        }
        return true;
    }

    public void inorder(TreeNode root, List<Integer> list) {
        if (root == null)
            return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }

    /**
     * hot100一刷
     * hot100二刷
     */
    public boolean isValidBST1(TreeNode root) {
        if (root.left == null && root.right == null)
            return true;
        boolean l = compare(root.left, Integer.MIN_VALUE, root.val);
        boolean r = compare(root.right, root.val, Integer.MAX_VALUE);
        return l && r;
    }

    public boolean compare(TreeNode root, int low, int high) {
        if (root == null)
            return true;
        if (root.val <= low || root.val >= high)
            return false;
        boolean l = compare(root.left, low, root.val);
        boolean r = compare(root.right, root.val, high);
        return l && r;
    }

}
